package leetcode_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *@author 周杨
 *Permutations_46 Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
 *describe: 求一个数组的全排列 不断调用求下一个排列的方法  详细见nextPermutation  用回溯更加直观
 *2018年5月5日 下午3:45:30
 */
public class Permutations_46 {
	List<List<Integer>> res=new ArrayList<List<Integer>>();
	public static void main(String[] args) {
		int nums[]=new int[] {1,1,2};
		Permutations_46 test=new Permutations_46();
		test.permute(nums);

	}
	
	/**
	 * describe:回溯 AC 50%
	 * 2018年12月25日 下午3:37:38
	 */
	public List<List<Integer>> permute1(int[] nums) {
		List<List<Integer>> res=new ArrayList<List<Integer>>();
		dfs(res,new ArrayList<Integer>(),nums,new boolean[nums.length]);
		return res;
	}
	
	public void dfs(List<List<Integer>> res,List<Integer> temp,int []nums,boolean visited[]) {
		if(temp.size()==nums.length) {
			List<Integer> t=new ArrayList<Integer>();
			t.addAll(temp);
			res.add(t);
			return ;
		}
		for(int i=0;i<nums.length;++i) {
			if(!visited[i]) {
				visited[i]=true;
				temp.add(nums[i]);
				dfs(res, temp, nums, visited);
				visited[i]=false;
				temp.remove(temp.size()-1);
			}
		}
	}
	
	public List<List<Integer>> permute(int[] nums) {
        Arrays.sort(nums);
        int count=1;
        for(int i=2;i<=nums.length;++i) {
        	count*=i;
        }
        for(int i=0;i<count;++i) {
        	List<Integer> list=new ArrayList<Integer>();
        	for(int j=0;j<nums.length;++j) {
        		list.add(nums[j]);
        	}
        	res.add(list);
        	nextPermutation(nums);	
        }
        return res;
    }
	
	public void nextPermutation(int[] nums) {
		int temp;
        for(int i=nums.length-2;i>=0;--i) {
        	if(nums[i]<nums[i+1]) {
        		for(int j=nums.length-1;j>i;--j) {
        			if(nums[j]>nums[i]) {
        				temp=nums[i];
        				nums[i]=nums[j];
        				nums[j]=temp;
        				reverse(i+1, nums.length-1, nums);
        				return;
        			}
        		}
        	}
        }
    }
	
	public void reverse(int i,int j,int nums[]) {
		int temp;
		while(i<j) {
			temp=nums[i];
			nums[i]=nums[j];
			nums[j]=temp;
			++i;
			--j;
		}
	}

}
